﻿#include <iostream>
#include <windows.h>
#include <stdlib.h>

using namespace std;

const int n = 1000;
int a[n], sum;
int sum1 = 0, sum2 = 0;

int main()
{
    long long head, tail, freq;//计时器



    for (int k = 64; k <= n; k *= 2) {

        for (int i = 0; i < k; i++)//初始化
        {
            a[i] = 1;
        }
        QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
        QueryPerformanceCounter((LARGE_INTEGER*)&head);

        
        //平凡算法
        for (int p = 0; p < 1000; p++) {
            for (int i = 0; i < n; i++)
                sum += a[i];

        }
        
        /*sum1 = 0; sum2 = 0；
            for (i = 0；i < n; i += 2)
            {
                sum1 += a[i];
                sum2 += a[i + 1];
            }
        sum = sum1 + sum2;*//*2路链式*/

        //*****************************************

        /*function recursion(n)
        {
            if (n == 1)
                return;
            else
            {
                for (i = 0; i < n / 2; i++)
                    a[i] += a[n − i − 1];
                n = n / 2;
                recursion(n);
            }
        }*//*递归函数*/

        //*****************************************

       /* for (m = n; m > 1; m /= 2)
            for (i = 0; i < m / 2; i++)
                a[i] = a[i ∗ 2] + a[i ∗ 2 + 1]*//*二重循环*/

        //*****************************************

        /*for (int i = 0; i < n; i += 4) {
            sum1 += a[i] + a[i + 1];
            sum2 += a[i + 2] + a[i + 3];
        }*//*unroll优化后的2路链式*/

        //********************************************

       /* for (int m = n; m > 1; m /= 2) {
            for (int i = 0; i < m / 2; i++)
            {
                a[i] = a[i * 2] + a[i * 2 + 1];
                a[i + 1] = a[i * 2 + 2] + a[i * 2 + 3];
            }*//*unroll优化后的双重循环*/

        //***************************************************

        /*function recursion(n)
        {
            if (n == 1)
                return;
            else
            {
                for (i = 0; i < n / 2; i += 2)
                    a[i] += a[n − i − 1];
                a[i + 1] += a[n − i − 2];
                n = n / 2;
                recursion(n);
            }
        }*//*unroll优化的递归*/

        QueryPerformanceCounter((LARGE_INTEGER*)&tail);
        //        cout<<k<<endl;
        cout << (tail - head) * 1000.0 / freq << endl;
        //cout<<sum<<endl;
    }
    return 0;
}